#include<iostream>
#include<queue>
#include<set>
#include <string>
using namespace std;

class Node
{
private:
	
	string Mystr;
	int depth;
	
public:
	string matchStr;
	set<Node*> Mychild;
	Node(const string &str,int fatherDepth,const string mstr)
	{
		matchStr=mstr;
		Mystr=str;
		depth=fatherDepth++;
		//GoFlag=true;
	}
	string getMystr()
	{
		return Mystr;
	}
	int getDepth()
	{
		return depth;
	}
};


void developTree(Node* thisNode,const set<string> &dic)
	{
		//bool tmpFlag=false;
		set<string>::iterator ele;
		for(ele=dic.begin();ele!=dic.end();++ele)
		{
			string element=*ele;
			if((thisNode->getMystr().find(element)==0))
			{
				//cout<<"construct Tree: "<<element<<endl;
				//tmpFlag=true;
				string part_str=thisNode->getMystr().substr(element.size());
				Node* child=new Node(part_str,thisNode->getDepth(),element);

				
				cout<<"Father is: "<<thisNode->getMystr()<<endl;
				cout<<"Mystr is: "<<child->getMystr()<<endl;
				cout<<"Match is: "<<child->matchStr<<endl;
				cout<<endl;
				
				thisNode->Mychild.insert(child);
				developTree(child,dic);
			}
		}
};

void visitDepth(Node* root,string str,set<string> &R)
{
	Node*t=root;
	if(t->getMystr()=="")
	{
		//str=str+t->matchStr;
		R.insert(str.substr(0,str.size()-1));
	}
	else
	{
	set<Node* >::iterator iter;
	for(iter=root->Mychild.begin();iter!=root->Mychild.end();iter++)
	{
		Node* t=*iter;
		if(t->matchStr!="")
		{
			//cout<<"Father is: "<<root->getMystr()<<endl;
			//cout<<"Mystr is: "<<t->getMystr()<<endl;
			//cout<<"str is: "<<str<<endl;
			//cout<<"match str is: "<<t->matchStr<<endl;
			//str=str+t->matchStr+" ";
			
			//cout<<endl;
		    visitDepth(t,str+t->matchStr+" ",R);
		}   

	}
}
}

void getResult(Node* root)
{
	set<string> R;
	set<Node* >::iterator iter;
}

void minicut(const string &str, const set<string> &dic)
{


}

void main()
{
	string s1="abcd";
	string s2="abcd";
	string s="";
	//size_t pos;
	//pos=s1.find(s2);
	//if (pos==0)
	//{
	 // cout<<pos;
	//}
     string S = "ilikealibaba";
	 set<string> D;
	 set<string> R;
	 D.insert("i");
	 D.insert("like");
	 D.insert("ali");
	 D.insert("liba");
	 D.insert("baba");
	 D.insert("alibaba");
	 //minicut(S, D);
	Node* root=new Node(S,0,"");
	developTree(root,D);
	visitDepth(root,s,R);
	//Node* child=new Node("ilike",0);
    //father->Mychild.insert(child);
	//Node* father=*(root->Mychild.begin());
	//set<Node* >::iterator iter;
	//for(iter=father->Mychild.begin();iter!=father->Mychild.end();iter++)
	//{
	//	Node * t=*iter;
	//	cout<<t->getMystr()<<endl;
	//}


	set<string>::iterator i;
      for(i=R.begin();i!=R.end();i++)
	{
		string s=*i;
		cout<<s<<endl;
		cout<<count(s.begin(),s.end(),' ')<<endl;
	}
	
	//cout<<root->getMystr();
}